package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202408;

public class leetcode20240819 {

    private static final int MOD=1000000007;
    private static final int MX=100001;
    private static final int[][][] memo=new int[MX][2][3];

    public int checkRecord(int n){
        return dfs(n,0,0);
    }

    private static int dfs(int i,int j,int k){
        if(i==0){
            return 1;
        }
        if(memo[i][j][k]>0){// 之前计算过
            return memo[i][j][k];
        }
        long res=dfs(i-1,j,0);// 填P
        if(j==0){
            res+=dfs(i-1,1,0);// 填A
        }
        if(k<2){
            res+=dfs(i-1,j,k+1);// 填L
        }
        return memo[i][j][k]=(int)(res%MOD);
    }
}
